package william.array;

/**
 * @author ZhangShenao
 * @date 2024/1/9
 * @description <a href="https://leetcode.cn/problems/move-zeroes/">...</a>
 */
public class Leetcode283_移动零 {
    /**
     * 采用双指针法
     * 指针i用于遍历数组元素,指针lastNonZero指向第一个非零元素,[0...lastNonZero)范围内的元素均为非零元素。lastNonZero从0开始
     * 遍历数组,如果当前元素不为0,则将当前元素与lastNonZero位置的元素交换,并将lastNonZero+1
     * 时间复杂度O(N)
     * 空间复杂度O(1)
     */
    public void moveZeroes(int[] nums) {
        //边界条件校验
        if (nums == null || nums.length < 2) {
            return;
        }

        //指针lastNonZero指向第一个非零元素,[0...lastNonZero)范围内的元素均为非零元素
        int lastNonZero = 0;

        //遍历数组
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) { //如果当前元素不为0,则将当前元素与lastNonZero位置的元素交换,并将lastNonZero+1
                if (i != lastNonZero) {
                    swap(nums, i, lastNonZero++);
                } else {    //所有元素都非零时,无需交换
                    lastNonZero++;
                }
            }
        }
    }

    /**
     * 交换数组i,j两个位置的元素
     */
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
